import numpy as np

np.random.seed(1)


def merge_sort(seq):
    seq_len = len(seq)
    if seq_len <= 1:  # 当只有一个关键字时的基例
        return seq
    middle = len(seq) // 2
    left_sorted_seq = merge_sort(seq[:middle])
    right_sorted_seq = merge_sort(seq[middle:])
    return while_merge(left_sorted_seq, right_sorted_seq)


def for_merge(left_seq: list, right_seq: list):
    """
    for加哨兵标记实现merge合并
    :param left_seq: 左边序列
    :param right_seq: 右边序列
    :return: 合并排序后的序列
    """
    sorted_seq = []
    i = j = 0
    max_float = float("inf")
    seq_len = len(left_seq) + len(right_seq)
    left_seq.append(max_float)
    right_seq.append(max_float)
    for k in range(seq_len):
        if left_seq[i] <= right_seq[j]:
            sorted_seq.append(left_seq[i])
            i += 1
        else:
            sorted_seq.append(right_seq[j])
            j += 1
    return sorted_seq


def while_merge(left_seq: list, right_seq: list):
    """
    while直接实现merge合并
    :param left_seq: 左边序列
    :param right_seq: 右边序列
    :return: 合并排序后的序列
    """
    sorted_seq = []
    i = j = 0
    while i < len(left_seq) and j < len(right_seq):
        if left_seq[i] <= right_seq[j]:
            sorted_seq.append(left_seq[i])
            i += 1
        else:
            sorted_seq.append(right_seq[j])
            j += 1
    while i < len(left_seq):
        sorted_seq.append(left_seq[i])
        i += 1
    while j < len(right_seq):
        sorted_seq.append(right_seq[j])
        j += 1
    return sorted_seq


if __name__ == '__main__':
    origin_ls = list(np.random.randint(-111, 2550, (2000,)))
    print(origin_ls)
    print(merge_sort(origin_ls))
